﻿#include<stdio.h>

typedef int Datatype;

//交换
void swap(Datatype* x, Datatype* y)
{
	Datatype temp = *x;
	*x = *y;
	*y = temp;
}

//向下调整
void Adjustdown(Datatype* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}

		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//找前k个最大的用小堆，前k个最小的用大堆
void printTopk(Datatype* arr, int k, int n)
{
	//建大小为k的大堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(arr, i, k);
	}

	//将后N-K个数据分别与堆顶元素比较，若小于堆顶元素，交换后进行向下调整
	for (int i = k; i < n; i++)
	{
		if (arr[i] < arr[0])
		{
			swap(&arr[i], &arr[0]);
			Adjustdown(arr, 0, k);
		}
	}

	//打印数组前k个数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", arr[i]);
	}
}